// https://www.lintcode.com/problem/edit-distance/description
// 滚动数组版本，空间复杂度O(N)
class Solution {
public:
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    int minDistance(string &word1, string &word2) {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> record(2, vector<int>(n + 1, 0));
        record[0][0] = 0;
        int now = 0;
        int past = 0;
    
        for (int i = 0; i <= m; ++i)
        {
            past = now;
            now = 1 - now;                                                                              
            for (int j = 0; j <= n; ++j)
            {
                if (i == 0)
                {
                    record[now][j] = j;
                    continue;
                }
                if (j == 0)
                {
                    record[now][j] = i;
                    continue;
                }
                if (word1[i - 1] == word2[j - 1]) 
                    record[now][j] = record[past][j - 1];
                else 
                    record[now][j] = min(min(record[past][j], record[now][j - 1]), record[past][j - 1]) + 1;
            }
        }
        return record[now][n];
    }
};